/**
 * 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
 *
 * 锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
 *
 * 列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
 *
 * 字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
 * 链接：https://leetcode.cn/problems/open-the-lock
 * 思路：双向BFS
 */
class OpenLock {
    String s,t;
    Set<String> set=new HashSet<>();
    public int openLock(String[] deadends, String target) {
        s="0000";
        t=target;
        if(s.equals(t))
        return 0;
        for(String deadend:deadends) {
            set.add(deadend);
        }
        if(set.contains(s)) {
            return -1;
        }
        int ans=bfs();
        return ans;
    }
    public int bfs() {
        //d1表示正向搜索
        //d2表示方向搜索
        Deque<String> d1=new LinkedList<>();
        Deque<String> d2=new LinkedList<>();
        //m1用来存d1枚举过的所有情况，m2用来存d2枚举过的所有情况
        Map<String,Integer> m1=new HashMap<>();
        Map<String,Integer> m2=new HashMap<>();
        d1.addLast(s);
        d2.addLast(t);
        m1.put(s,0);
        m2.put(t,0);
        while(!d1.isEmpty()&&!d2.isEmpty()) {
            int t=-1;
            if(d1.size()<=d2.size()) {
                t=update(d1,m1,m2);
            } else {
                t=update(d2,m2,m1);
            }
            if(t!=-1) {
                return t;
            }
        }
        return -1;
    }
    public int update(Deque<String> qu,Map<String,Integer> cur,Map<String,Integer> other) {
        int size=qu.size();
        while(size-->0) {
            String poll=qu.pollFirst();
            char[] pcs=poll.toCharArray();
            int step=cur.get(poll);
            for(int i=0;i<4;i++) {
                for(int j=-1;j<=1;j++) {
                    if(j==0) {
                        continue;
                    }
                    char[] clone=pcs.clone();
                    int orgin=pcs[i]-'0';
                    int next=(orgin+j)%10;
                    if(next==-1) {
                        next=9;
                    }
                    clone[i]=(char)(next+'0');
                    String tmp=String.valueOf(clone);
                    if(set.contains(tmp)) {
                        continue;
                    }
                    if(cur.containsKey(tmp)) {
                        continue;
                    }
                    if(other.containsKey(tmp)) {
                        return step+other.get(tmp)+1;
                    } else {
                        qu.addLast(tmp);
                    cur.put(tmp,step+1);
                    }
                    
                }
            }
        }
        return -1;
    }
}